package com.xupt.easy.array;

/**
 * @author zhaoxin
 * @title: SearchInsert
 * @projectName LeetCode
 * @description: 搜索插入位置
 * @date 2019/11/19 13:07
 */
public class SearchInsert035 {

    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     *
     * 你可以假设数组中无重复元素。
     *
     * 示例 1:
     *
     * 输入: [1,3,5,6], 5
     * 输出: 2
     *
     * 示例 2:
     *
     * 输入: [1,3,5,6], 2
     * 输出: 1
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        // 二分查找法
        int len = nums.length;
        int left = 0;
        int right = len - 1;

        while(left <= right){
            int mid = (right + left) / 2;
            if (nums[mid] < target){
                left = mid + 1;
            }else if (nums[mid] > target){
                right = mid - 1;
            }else {
                return mid;
            }
        }

        return left;
    }


    public static void main(String[] args) {
        int [] arr = {1,3,5,6};
        int target = 2;
        SearchInsert035 searchInsert035 = new SearchInsert035();
        searchInsert035.searchInsert(arr, target);

    }

}
